package project;

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;

public class Astar {
	
	private static int heuristic(int player, int y) {
		return (player == 0) ? 8-y :y;
	}
	
	private static boolean inbounds(int what) {
		return 0 <= what && what <= 8;
	}
	
	/**
	 * Calculates the minimum distance between a pawn and its goal
	 * @param player The player whose path you wish to determine
	 * @param game The game in which you wish to find a player's shortest path
	 * @return The length of the shortest path for "player" to get to their goal
	 */
	protected static int findDist(int player, GameState game) {
		int[][] dist = new int[9][9];
		int[][] seen = new int[9][9];
		
		ArrayList<LinkedList<Point>> bucket = new ArrayList<LinkedList<Point>>(82);
		int cb = 0;
		int i, j;
		int x, y;
		int dx[] = {-1, 0, 1, 0};
		int dy[] = {0, 1, 0, -1};
		
		for (i = 0; i <= 82; i++) {
			bucket.add(new LinkedList<Point>());
		}
		for (i = 0; i < 9; i++) {
			for (j = 0; j < 9; j++) {
				dist[i][j] = Integer.MAX_VALUE;
				seen[i][j] = 0;
			}
		}
		
		x = game.players[player].getX();
		y = game.players[player].getY();
		dist[x][y] = 0;
		
		while (heuristic(player, y) != 0) {
		 
			seen[x][y] = 1;
			
			for (i = 0; i < 4; i++) {
				if (!inbounds(x+dx[i]) || !inbounds(y+dy[i]))
					continue;
				if (game.grid[(4*x + 2*dx[i])/2][(4*y + 2*dy[i])/2] != GameState.EMPTY)
					continue;
				if (dist[x][y] + 1 >= dist[x+dx[i]][y+dy[i]])
					continue;
				
				dist[x+dx[i]][y+dy[i]] = dist[x][y]+1;
				bucket.get(dist[x][y] + 1 + heuristic(player, y+dy[i])).add(new Point(x + dx[i], y + dy[i]));
			}
			
			Point temp;
			do {
				while (cb < 82 && bucket.get(cb).isEmpty())
					cb++;
				 
				if (cb >= 82)
					return -1;
				 
				temp = bucket.get(cb).remove();
			} while (seen[temp.x][temp.y] != 0);
			
			x = temp.x;
			y = temp.y;
		}
		
		return dist[x][y];
	}
}